package com.fps.webshop.question.question0100_0199;

import com.fps.webshop.question.question0700_0799.Question704;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 169. 多数元素
 * 
 * 给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于"n/2"的元素。
 *
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 *
 * 示例1：
 * 输入：[3,2,3]
 * 输出：3
 *
 * 示例2：
 * 输入：[2,2,1,1,1,2,2]
 * 输出：2
 *
 * 进阶：
 * 		尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
 *
 */
public class Question169 {
	
	
	/**
	 * 第一次提交，使用HashMap进行记录，不符合进阶的要求，也比较慢速
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		13 ms	43.7 MB	Java	2021/09/06 09:53
	 * 
	 * 执行用时：13 ms, 在所有 Java 提交中击败了22.47%的用户
	 * 内存消耗：43.7 MB, 在所有 Java 提交中击败了83.39%的用户
	 */
	public static int majorityElement(int[] nums) {
		if(nums.length==1){
			return nums[0];
		}
		Map<Integer,Integer> map = new HashMap<>();
		int min = nums.length/2;
		for(int a: nums){
			if(map.get(a)==null){
				map.put(a,1);
			}else{
				int i = map.get(a)+1;
				if(i>min){
					return a;
				}else{
					map.put(a,i);
				}
			}
		}
		return -1;
	}

	/**
	 * 第2次提交，尝试使用数组进行记录，但没考虑到负数，当数字中存在负数的时候，数组下标不合法
	 *
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 不通过
	 *
	 */
	public static int majorityElement2(int[] nums) {
		if(nums.length==1){
			return nums[0];
		}
		int min = nums.length/2;
		int max = nums[0];
		for(int a: nums){
			max = Math.max(max,a);
		}
		int a[] = new int[max+1];
		for(int i: nums){
			if(a[i]+1>min){
				return i;
			}else{
				a[i]++;
			}
		}
		return -1;
	}


	/**
	 * 第3次提交，尝试使用摩尔投票法
	 *
	 * 摩尔投票法：
	 * 核心就是对拼消耗。
	 * 玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。
	 * 那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），
	 * 但是只要你们不要内斗，最后肯定你赢。
	 * 最后能剩下的必定是自己人。
	 *
	 * 解法：先假设第一个数过半数并设cnt=1；遍历后面的数如果相同则cnt+1，不同则减一，
	 * 当cnt为0时则更换新的数字为候选数（成立前提：有出现次数大于n/2的数存在）
	 *
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		1 ms	43.8 MB	Java	2021/09/06 10:22
	 *
	 * 执行用时：1 ms, 在所有 Java 提交中击败了99.96%的用户
	 * 内存消耗：43.8 MB, 在所有 Java 提交中击败了76.77%的用户
	 *
	 */
	public static int majorityElement3(int[] nums) {
		int res=0,cnt=0;
		for(int i=0;i<nums.length;i++){
			if(cnt==0) {
				res=nums[i];
				cnt++;
			}else{
				if(res==nums[i]){
					cnt++;
				}else {
					cnt--;
				}
			}
		}
		return res;
	}

	/**
	 * 第4次提交，取巧，先排序，再去中间的数，因为大于多数，所以中间的数必是
	 *
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		2 ms	44.3 MB	Java	2021/09/06 10:24
	 *
	 * 执行用时：2 ms, 在所有 Java 提交中击败了61.24%的用户
	 * 内存消耗：44.3 MB, 在所有 Java 提交中击败了41.54%的用户
	 *
	 */
	public int majorityElement4(int[] nums) {
		Arrays.sort(nums);
		return nums[nums.length / 2];
	}

	/**
	 * 第5次提交，位运算
	 *
	 * 位运算法,统计每个数字每一位0，1出现的次数，如果某一位1出现的次数多则该位为1，0同理；
	 * 最后按为统计出来的数就是众数
	 *
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注
	 * 通过		6 ms	44.3 MB	Java	2021/09/06 10:32
	 *
	 * 执行用时：6 ms, 在所有 Java 提交中击败了27.27%的用户
	 * 内存消耗：44.3 MB, 在所有 Java 提交中击败了39.13%的用户
	 *
	 */
	public int majorityElement5(int[] nums) {
		int res=0,len = nums.length;
		for(int i=0;i<32;i++){
			int ones=0,zero=0;
			for(int j=0;j < len; j++){
				if(ones>len/2 ||zero>len/2) break;
				if((nums[j]&(1<<i)) != 0) ones++;
				else zero++;
			}
			if(ones > zero)
				res = res|(1<<i);
		}
		return res;
	}
	
	public static void main(String[] args) {
		int[] theList = new int[] {3,2,3};
		 
		System.out.print(majorityElement(theList));
	}
}
